{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Car Pooling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum #sorting #simulation #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和 #排序 #模拟 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: carPooling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #拼车"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>车上最初有&nbsp;<code>capacity</code>&nbsp;个空座位。车&nbsp;<strong>只能&nbsp;</strong>向一个方向行驶（也就是说，<strong>不允许掉头或改变方向</strong>）</p>\n",
    "\n",
    "<p>给定整数&nbsp;<code>capacity</code>&nbsp;和一个数组 <code>trips</code> , &nbsp;<code>trip[i] = [numPassengers<sub>i</sub>, from<sub>i</sub>, to<sub>i</sub>]</code>&nbsp;表示第 <code>i</code> 次旅行有&nbsp;<code>numPassengers<sub>i</sub></code>&nbsp;乘客，接他们和放他们的位置分别是&nbsp;<code>from<sub>i</sub></code>&nbsp;和&nbsp;<code>to<sub>i</sub></code>&nbsp;。这些位置是从汽车的初始位置向东的公里数。</p>\n",
    "\n",
    "<p>当且仅当你可以在所有给定的行程中接送所有乘客时，返回&nbsp;<code>true</code>，否则请返回 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>trips = [[2,1,5],[3,3,7]], capacity = 4\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>trips = [[2,1,5],[3,3,7]], capacity = 5\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= trips.length &lt;= 1000</code></li>\n",
    "\t<li><code>trips[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= numPassengers<sub>i</sub>&nbsp;&lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= from<sub>i</sub>&nbsp;&lt; to<sub>i</sub>&nbsp;&lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= capacity &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [car-pooling](https://leetcode.cn/problems/car-pooling/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [car-pooling](https://leetcode.cn/problems/car-pooling/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,1,5],[3,3,7]]\\n4', '[[2,1,5],[3,3,7]]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        trips.sort(key = lambda x: x[1])\n",
    "        minheap = []\n",
    "        headcount = 0\n",
    "        for num, start, end in trips:\n",
    "            while minheap and minheap[0][0] <= start:\n",
    "                headcount -= minheap[0][1]\n",
    "                heapq.heappop(minheap)\n",
    "            heapq.heappush(minheap, (end, num))\n",
    "            headcount += num\n",
    "            if headcount > capacity:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        locationCapacity = [0 for i in range(1001)]\n",
    "        for trip in trips:\n",
    "            num_passengers = trip[0]\n",
    "            start_location = trip[1]\n",
    "            end_location = trip[2]\n",
    "            for i in range(start_location, end_location):\n",
    "                locationCapacity[i] += num_passengers\n",
    "                if locationCapacity[i] > capacity:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        dp = [0]*1000\n",
    "        max_cap = 0\n",
    "        for trip in trips:\n",
    "            for i in range(trip[1],trip[2]):\n",
    "                dp[i] += trip[0]\n",
    "                if dp[i] > max_cap:\n",
    "                    max_cap = dp[i]\n",
    "        if max_cap > capacity:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips, capacity: int) -> bool:\n",
    "        #检测是否存在一个时间点，超员\n",
    "        from collections import defaultdict\n",
    "        fuck=defaultdict(int)\n",
    "        for num_passengers,start,end in trips:\n",
    "            for x in range(start,end):\n",
    "                fuck[x]+=num_passengers\n",
    "                if fuck[x]>capacity:\n",
    "                    return False\n",
    "        return True\n",
    "# fuck=Solution()\n",
    "# print(fuck.carPooling(trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        trips.sort(key=lambda t: t[1])\n",
    "        heap = []\n",
    "        carry = 0\n",
    "        for num, start, end in trips:\n",
    "            while heap and heap[0][0] <= start:\n",
    "                _, getoff = heappop(heap)\n",
    "                carry -= getoff\n",
    "            heappush(heap, (end, num))\n",
    "            carry += num\n",
    "            if carry > capacity:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        res=[0 for i in range(1001)]\n",
    "        for t in trips:\n",
    "            for i in range(t[1],t[2]):\n",
    "                res[i]+=t[0]\n",
    "        for r in res:\n",
    "            if r>capacity:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        trips.sort(key=lambda e: e[1])\n",
    "        cu, deque = 0, []\n",
    "        for e in trips:\n",
    "            next_deque = []\n",
    "            for x in deque:\n",
    "                if e[1] >= x[2]:\n",
    "                    cu -= x[0]\n",
    "                else:\n",
    "                    next_deque.append(x)\n",
    "            cu += e[0]\n",
    "            if cu > capacity:\n",
    "                return False\n",
    "            deque = next_deque\n",
    "            deque.append(e)\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips, capacity: int) -> bool:\n",
    "        trips.sort(key=lambda val: val[1])  # 按照出发站的顺序依次上车\n",
    "\n",
    "        temp_trips = trips[:]\n",
    "        temp_trips.sort(key=lambda val: val[2])\n",
    "        last = temp_trips[-1][2]  # 最后一站\n",
    "\n",
    "        left = capacity  # 车内的剩余容量\n",
    "        end_people = dict()  # 已上车乘客的终点站信息及其人数\n",
    "\n",
    "        for cur in range(1, last+1):\n",
    "            if cur in end_people.keys():  # 当前站有人下\n",
    "                left += end_people[cur]  # 下车\n",
    "                end_people.pop(cur)  # 删除已下车乘客的信息\n",
    "\n",
    "            if not trips:  # 可能没有待上车乘客\n",
    "                continue\n",
    "            while trips[0][1] == cur:  # 当前站有人上\n",
    "                if trips[0][0] > left:  # 不能全部上车\n",
    "                    return False\n",
    "                left -= trips[0][0]  # 上车\n",
    "                if trips[0][2] in end_people.keys():\n",
    "                    end_people[trips[0][2]] += trips[0][0]\n",
    "                else:\n",
    "                    end_people[trips[0][2]] = trips[0][0]\n",
    "                trips.pop(0)  # 删除已上车乘客的信息\n",
    "                if not trips:\n",
    "                    break\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        n = len(trips)\n",
    "        curr_diff = [0] * 1001\n",
    "        for i in range(n):\n",
    "            curr_diff[trips[i][1]] += trips[i][0]\n",
    "            curr_diff[trips[i][2]] -= trips[i][0]\n",
    "        total = 0\n",
    "        for i in range(1, 1001):\n",
    "            total += curr_diff[i]\n",
    "            if total > capacity:\n",
    "                return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        d = {}\n",
    "        for item in trips:\n",
    "            d[item[1]] = d.get(item[1], 0) + item[0]\n",
    "            d[item[2]] = d.get(item[2], 0) - item[0]\n",
    "\n",
    "        d = sorted(d.items(), key=lambda x: x[0])\n",
    "        r = 0\n",
    "        for i in d:\n",
    "            r = r + i[1]\n",
    "            if r > capacity:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        ans = [0 for i in range(1001)]\n",
    "        len_trips = len(trips)\n",
    "\n",
    "        for i in range(len_trips):\n",
    "            ans[trips[i][1]] += trips[i][0]\n",
    "            ans[trips[i][2]] -= trips[i][0]\n",
    "        \n",
    "        for i in range(1,1001):\n",
    "            ans[i] += ans[i - 1]\n",
    "            if ans[i] > capacity:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        # 19:25 -\n",
    "        # 思路： 构建列表\n",
    "        x = [0 for _ in range(100001)]\n",
    "        for wd in trips:\n",
    "            for position in range(wd[1], wd[2]):\n",
    "                x[position] += wd[0]\n",
    "        if max(x)>capacity:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        # diff = [0] * 1002\n",
    "        # for x, l, r in trips:\n",
    "        #     diff[l] += x\n",
    "        #     diff[r] -= x\n",
    "        # if diff[0] > capacity:\n",
    "        #     return False\n",
    "        # for i in range(1, len(diff)):\n",
    "        #     diff[i] += diff[i - 1]\n",
    "        #     if diff[i] > capacity:\n",
    "        #         return False\n",
    "        # return True\n",
    "        diff = [0] * 1002\n",
    "        for x, l, r in trips:\n",
    "            diff[l] += x\n",
    "            diff[r] -= x\n",
    "\n",
    "        if diff[0] > capacity:\n",
    "            return False\n",
    "        for i in range(1, len(diff)):\n",
    "            diff[i] += diff[i - 1]\n",
    "            if diff[i] > capacity:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        f = [0 for _ in range(1002)]\n",
    "\n",
    "        for x, L, R in trips:       #差分统计的思想   台阶，上下楼梯的思想\n",
    "            f[L] += x\n",
    "            f[R] -= x\n",
    "            \n",
    "        if f[0] > capacity:\n",
    "            return False\n",
    "        for i in range(1, 1002):\n",
    "            f[i] = f[i-1] + f[i]\n",
    "            if f[i] > capacity:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        cars = [0] * 1001\n",
    "        for i in trips:\n",
    "            cars[i[1]] += i[0]\n",
    "            cars[i[2]] -= i[0]\n",
    "        sum = 0\n",
    "        for i in range(len(cars)):\n",
    "            sum = sum + cars[i]\n",
    "            if sum > capacity:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        dic={}\n",
    "        for i in range(len(trips)):\n",
    "            for j in range(trips[i][1],trips[i][2]):\n",
    "                if(j in dic):\n",
    "                    dic[j]+=trips[i][0]                \n",
    "                else:\n",
    "                    dic.setdefault(j,trips[i][0])\n",
    "                if(dic[j]>capacity):\n",
    "                        return False;\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        trips.sort(key=lambda x:x[-1],reverse=False)\n",
    "        print(trips)\n",
    "        diff = [0] * (trips[-1][2] + 1)\n",
    "        for i in range(len(trips)):\n",
    "            nums, start, left = trips[i][0], trips[i][1], trips[i][2]\n",
    "            for j in range(start, left):\n",
    "                diff[j] += nums\n",
    "                if diff[j] > capacity:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        rec1 = []\n",
    "        rec2 = []\n",
    "        for i, j in enumerate(trips):\n",
    "            rec1.append([j[1], j[0]])\n",
    "            rec2.append([j[2], -j[0]])\n",
    "     \n",
    "        rec = rec1 + rec2\n",
    "        rec = sorted(rec, key = lambda x:[x[0], x[1]])\n",
    "        print(rec)\n",
    "        cur = 0\n",
    "        for i in rec:\n",
    "            cur += i[1]\n",
    "            if cur > capacity:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        d = [0] * 1001\n",
    "        for i, s, t in trips:\n",
    "            d[s] += i\n",
    "            d[t] -= i\n",
    "        return all(s <= capacity for s in accumulate(d))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        d = [0] * 1001\n",
    "        for num, from_, to in trips:\n",
    "            d[from_] += num\n",
    "            d[to] -= num\n",
    "        return all(s <= capacity for s in accumulate(d))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        diff = [0] * 1001\n",
    "        for x, f, t in trips:\n",
    "            diff[f] += x\n",
    "            diff[t] -= x\n",
    "        p = list(accumulate(diff))\n",
    "        return all(x <= capacity for x in p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:\n",
    "        s_trip = sorted(trips,key = lambda x:x[2])\n",
    "        max_trip = s_trip[-1][2]\n",
    "        person_list = [0]*(max_trip+1)\n",
    "        for p,i,j in trips:\n",
    "            idx = i\n",
    "            while idx<j and person_list[idx]+p<=capacity:\n",
    "                person_list[idx]+=p\n",
    "                idx +=1\n",
    "            if idx!=j:\n",
    "                return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
